package difficulty;//给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
//
//
//
// 示例 1：
//
//
//
//
//输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
//输出：6
//解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
//
//
// 示例 2：
//
//
//输入：height = [4,2,0,3,2,5]
//输出：9
//
//
//
//
// 提示：
//
//
// n == height.length
// 0 <= n <= 3 * 104
// 0 <= height[i] <= 105
//
// Related Topics 栈 数组 双指针 动态规划 单调栈
// 👍 2552 👎 0


import java.util.ArrayDeque;
import java.util.Deque;

//leetcode submit region begin(Prohibit modification and deletion)
public class L42 {

    public static void main(String[] args) {
        System.out.println(trap(new int[]{0, 7, 1, 4, 6}));
    }

    public static int trap(int[] height) {
        Deque<Integer> deque = new ArrayDeque<>();
        //单调递减
        int result = 0;
        for (int i = 0; i < height.length; i++) {
            while (deque.peekLast() != null && height[deque.peekFirst()] <= height[i]) {
                //结算开始
                int currentHeight = deque.pollLast();//1
                Integer firstHeight = deque.peekFirst();
                if (firstHeight == null) {
                    break;
                }
                result += (height[firstHeight] - height[currentHeight]);
            }
            deque.offerLast(i);
        }
        int rightHeight = 0;
        while (deque.size() > 1) {
            Integer currentHeight = deque.pollLast();
            int preHeight = deque.peekLast();
            rightHeight = Math.max(height[currentHeight], rightHeight);
            int h = rightHeight - height[preHeight];
            result += h > 0 ? h : 0;
        }
        return result;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
